//game
#include "game.h"
using namespace std;

vector<int> guess(int n, int limit) {
	vector<int> ans, ak;
	ans.resize(n);
    ak.resize(n);
    int cnt = 0;
	for(int i = 1; i <= n; i ++)
		ans[i - 1] = i;
    static int ban[5010], dq[5010], rp[5010];
    for(int i = 1; i <= n; ++ i){
        rp[i] = i;
    }
    random_shuffle(rp + 1, rp + n + 1);
    memset(ban, 0, sizeof(ban));
    for(int p = 0; p < n;){
        if(p == n - 1){
            for(int i = 1; i <= n; ++ i){
                if(!ban[i]){
                    ans[n-1] = i;
                }
            }
            break;
        }
        bool ok = 0;
        memcpy(dq, ban, sizeof(dq));
        for(int ii = 1; ii <= n; ++ ii){
            int i = rp[ii];
            if(ban[i]) continue;
            int cc = 0;
            for(int jj = 1; jj <= n; ++ jj){
                int j = rp[jj];
                if(i == j || dq[j]) continue;
                ak[p] = i, ak[p+1] = j;
                for(int k = 1, cnt = p+1; k <= n; ++ k){
                    if(k != i && k != j && !ban[k]) ak[++cnt] = k;
                }
                int x = count(ak);
                swap(ak[p], ak[p+1]);
                int y = count(ak);
                cnt += 2;
                if(x == y){
                    dq[j] = 1;
                    break;
                } else if(x - 2 == y){
                    ans[p] = ak[p] = i;
                    ans[p+1] = ak[p+1] = j;
                    ban[i] = ban[j] = 1;
                    ok = 1;
                    p += 2;
                    break;
                } else if(y - 2 == x){
                    ans[p] = ak[p] = j;
                    ans[p+1] = ak[p+1] = i;
                    ban[i] = ban[j] = 1;
                    ok = 1;
                    p += 2;
                    break;
                } 
                // else if(x - 1 == y){
                //     ++ cc;
                //     if(cc >= 2){
                //         ans[p] = ak[p] = i;
                //         ban[i] = 1;
                //         ok = 1;
                //         ++ p;
                //         break;
                //     }
                // }
            }
            if(ok) break;
        }
    }
	return ans;
}